package com.feiyue.learning.recursive;

import java.util.Scanner;

/**
 * 使用广度优先遍历处理最少转机问题(1->5)
 *      1·········2
 *         ·    · ·
 *          3     ·
 *        ·    ·  ·
 *      5·········4
 * @author  feiyue
 * @date  2020/4/5
 */
public class BreadthFirst {

    private static int minCount = 9999;

    public static void main(String[] args) {

        // 二维数组表示顶点间相连情况(1-相连, 0-不相连)
        int[][] route = new int[21][21];

        for (int i = 1; i < route.length; i++) {
            for (int j = 1; j < route.length; j++ ) {
                if (i == j) {
                    // 自己飞自己距离为0
                    route[i][j] = 0;
                } else {
                    // 初始化城市之间不可达
                    route[i][j] = 2;
                }
            }
        }

        for (int i = 0; i < 7; i++) {
            Scanner sc = new Scanner(System.in);
            System.out.println("输入相连的航班, 空格分离: ");

            String[] s = sc.nextLine().split(" ");
            int begin = Integer.valueOf(s[0]);
            int end = Integer.valueOf(s[1]);

            // route[begin][end] = 1, 表示 begin->end 存在航班
            route[begin][end] = 1;
            route[end][begin] = 1;
        }

        findMinExchangeRoute(route, 1, 5);

        System.out.println("1-->5 最少转机数：" + minCount);
    }

    /**
     * 广度优先遍历
     */
    private static void findMinExchangeRoute(int[][] route, int beginCity, int end) {
        Node[] nodes = new Node[26];

        // 当前队列的首部节点
        int cur;

        // 是否抵达终点
        int flag = 0;

        // 表示城市是否在队列中
        int[] book = new int[6];

        // 初始化队列首尾指针，头指针指向队列第一个元素，尾指针指向最后一个元素的后一个元素
        int head = 1, tail = 1;

        // 第一个城市入队列
        Node node = new Node(beginCity, 0);
        nodes[tail] = node;
        tail++;
        book[beginCity] = 1;

        while (head < tail) {
            cur = nodes[head].city;

            for (int i = 1; i < book.length; i++) {
                if (route[cur][i] == 1 && book[i] == 0) {
                    Node n = new Node(i, nodes[head].quantity + 1);
                    nodes[tail] = n;
                    tail++;

                    book[i] = 1;
                }

                if (nodes[tail - 1].city == end) {
                    flag = 1;
                    break;
                }
            }

            if (flag == 1) {
                minCount = nodes[tail - 1].quantity;
                break;
            }
            head++;
        }
    }
}

class Node {

    // 当前城市
    int city;

    // 距离起点的转机数
    int quantity;

    Node(int city, int quantity) {
        this.city = city;
        this.quantity = quantity;
    }
}